#!/usr/bin/python3

import numpy as np
import sys
from collections import deque


map_file=sys.argv[1]
grip = np.loadtxt(map_file,dtype=int)
l,w=grip.shape
if len(sys.argv)!=6:
    print("正确的格式为：program_file map_file <start_x> <start_y> <goal_x> <goal_y>")
    sys.exit(1)
start_x,start_y,goal_x,goal_y=map(int,sys.argv[2:])

start=(start_x,start_y)
goal=(goal_x,goal_y)
DIRS=[(0,1),(0,-1),(-1,0),(1,0)]

def in_bounds(r,c):
    return 0<=r <l and 0<=c<w

def is_open(r,c):
    return grip[r,c]==0

def bfs_path(grip,start,goal):
    visited={start}
    queue=deque([start])
    parent={start:None}
    while queue:
        cur=queue.popleft()
        if cur==goal:
            break
        r,c = cur
        for dr,dc in DIRS:
            nr,nc=r+dr,c+dc
            nxt=(nr,nc)
            if in_bounds(nr,nc) and is_open(nr,nc) and nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
                parent[nxt]=cur
    if goal not in parent:
        return None

    path=[]
    #路径回溯
    cur=goal
    while cur is not None:
        path.append(cur)
        cur=parent[cur]
    path.reverse()
    return path
def render_path(path):
    char_map=grip.tolist()
    for (r,c)in path:
        char_map[r][c]='*'

    for raw in char_map:
        print(" ".join(map(str,raw)))


def main():
    sr,sc=start
    gr,gc=goal
    if not in_bounds(sr,sc) or not in_bounds(gr,gc) or not is_open(sr,sc) or not is_open(gr,gc):
        print("起点/终点不合法/不可走")
        return
    path=bfs_path(grip,start,goal)
    if path is not None:
        render_path(path)


if __name__=="__main__":
    main()

